import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    //等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if(n <= 2) return 0;
        int[] dp = new int[n];
        int sum = 0;
        for(int i = 2; i < n; i++){
            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){
                dp[i] = dp[i-1] + 1;
                sum += dp[i];
            }
        }
        return sum;
    }
    //最长湍流子数组
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int ret = 1;
        //创建dp表
        int[] f = new int[n];//上升
        int[] g = new int[n];//下降
        //初始化
        for(int i = 0; i < n; i++){
            f[i] = 1;
            g[i] = 1;
        }
        //填表
        for(int i = 1; i < n; i++){
            if(arr[i] - arr[i-1] > 0) f[i] = g[i-1] + 1;
            else if(arr[i] - arr[i-1] < 0) g[i] = f[i-1] + 1;
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }
    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash = new HashSet<>(wordDict);
        int n = s.length();
        s = " " + s;
        //创建dp表
        boolean[] dp = new boolean[n+1];
        //初始化
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = i; j > 0; j--){
                if(dp[j-1] && hash.contains(s.substring(j, i+1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
    //环绕字符串中的唯一子字符串
    public int findSubstringInWraproundString(String s) {
        char[] chs = s.toCharArray();
        int n = chs.length;
        int[] hash = new int[26];
        //创建dp表
        int[] dp = new int[n];
        //初始化
        dp[0] = 1;
        hash[chs[0] - 'a'] = 1;
        //填表
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            if(chs[i] == chs[i-1] + 1 || chs[i] == 'a' && chs[i-1] == 'z'){
                dp[i] += dp[i-1];
            }
            //判断是否需要更新
            int index = chs[i] - 'a';
            hash[index] = Math.max(hash[index], dp[i]);
        }
        //返回
        int ret = 0;
        for(int i = 0; i < 26; i++){
            ret += hash[i];
        }
        return ret;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {9, 9};
        solution.maxTurbulenceSize(arr);
    }
}